package com.topInterview;

public class leecode309 {
    public int maxProfit(int k, int[] arr) {
        if (arr.length < 2) {
            return 0;
        }

        int N = arr.length;
        //buy[i]表示0~i位置最后一次买的操作，买的操作可能再i位置，也可能再0~i-1位置
        int[] buy = new int[N];
        //sell[i] 表示0~i位置最后一次卖的操作，卖的操作可能再i位置，也可能再0~i-1位置
        int[] sell = new int[N];
        buy[1] = Math.max(-arr[0], -arr[1]);
        sell[1] = Math.max(0, arr[1] - arr[0]);
        for (int i = 2; i < arr.length; i++) {
            buy[i] = Math.max(buy[i - 1], sell[i - 2] + arr[i]);
            sell[i] = Math.max(sell[i - 1], buy[i - 1] + arr[i]);
        }

        return sell[N - 1];

    }

}
